Codeforces Round #581 Div2 A~D题解

本场链接:Codeforces Round #581 Div2

闲话

速度很拉胯,不够写D的.赛后发现比赛场上想写出D还是有点差距感觉.

A. BowWow and the Timetable

原题大意:给你一个整数,问比他严格小的形如4k4^k的数的个数.原数非常大,输入为原数的二进制表示的字符串.
数据范围:
0s21000 \leq s \leq 2^{100}

思路

一个比较好想到的点是44无非就是两个22,答案还要算上00,所以就是长度nn的前提下,n/2n/2.如果除了第一位之外全是00,这个是对的,因为本身表示的那个数取不到,他得是严格大于,如果有一个,就可以取到.因此还要加一个判断看是不是后面完全都是00的.到这里其实还差一点,因为之前的分析的的前提是这个数可以表示成一个44的幂的形式,但是如果22的指数是一个奇数,就不能表示了.因此只有偶数次幂的时候,有那个看是否全是00的判断,否则就没有.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	string s;cin >> s;
	int n = s.size();
	int ok = 0;
	for(int i = 1;i < n;++i)
		if(s[i] != '0')
			ok = 1;
	printf("%lld\n",n / 2 + (n % 2 == 1 ? ok : 0));
    return 0;
}

B. Mislove Has Lost an Array

原题大意:构造一个长度为nn的序列,要求里面不同的元素的个数在[l,r][l,r]之间.并且每个元素要么是11,要么是一个偶数,对于一个偶数的元素aia_i,必须保证ai/2a_i/2是存在于这个序列里的.问这个序列最小和最大的总和分别是多少.
数据范围:
1n10001 \leq n \leq 1000
1lrmin(n,20)1 \leq l \leq r \leq min(n,20)

思路

由于这个题目的条件特别的强,导致了每个元素其实都是22的幂,所以可以从这个方向下手.又要保证说整个序列里不同的元素数量要在一个区间内,而这个区间的长度很小,所以可以枚举区间里的每一个数,直接遍历.假设当前要算的结果的是整个序列里有ii个不同元素的,那么最小的时候,就是尽量塞11进去,但是又要满足不同数量,所以完全可以只搞出ii个幂,就是1,2,4,...2i1,2,4,...2^i这一段,剩下的全部填11,这样就最小了,最大的也是同理,只要让后面的全部填2i2^i就可以了.最后全套一遍就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmul(ll a, ll b) 
{
  	ll L = a * (b >> 25LL)  * (1LL << 25) ;
  	ll R = a * (b & ((1LL << 25) - 1)) ;
  	return (L + R);
}
ll qpow(ll a,ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1)	res = qmul(res,a);
		a = qmul(a,a);
		b >>= 1;
	}
	return res;
}
int main()
{
	int n,l,r;cin >> n >> l >> r;
	ll minv = qpow(2,l) - 1 + n - l;
	ll maxv = qpow(2,r) - 1 + (n - r) * qpow(2,r - 1);
	for(int i = l;i <= r;++i)
	{
		ll A = qpow(2,i) - 1 + n - i,B = qpow(2,i) - 1 + (n - i) * qpow(2,i - 1);
		minv = min({minv,A,B});
		maxv = max({maxv,A,B});
	}

	cout << minv << " " << maxv << endl;
    return 0;
}

C. Anna, Svyatoslav and Maps

原题大意:没法翻译,自行看题.

数据范围:
2n1002 \leq n \leq 100

思路

定义关键点:一个关键点是线路上最短路必经的点,也就是序列里不会被删掉的点,显然p1,pmp_1,p_m是关键点.顺序考虑每个点,如果当前这个pip_i是一个关键点的话,意味着从上一个关键点走到pi+1p_{i+1}是必须要经过pip_i的,才会保留这个pip_i.设上一个关键点是uu,必须要经过的条件就是u>piu->p_i的距离不等于pi>pi+1p_i->p_{i+1}的距离减掉11.一旦删掉,这条路就会被一个最短路的点替代掉.所以做法已经非常显然了,就是跑一个floydfloyd求出任意两点距离,再按照从前往后的顺序遍历找到所有的关键点就可以了,

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105,M = 1e6+7;
char _g[N][N];
int g[N][N],f[N][N];
int p[M];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%s",_g[i] + 1);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			f[i][j] = int(_g[i][j] - '0');
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
			if(!f[i][j])
				f[i][j] = 0x3f3f3f3f;
		f[i][i] = 0;
	}
		
	//floyd
	for(int k = 1;k <= n;++k)
		for(int i = 1;i <= n;++i)
			for(int j = 1;j <= n;++j)
				f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
				
	int m;scanf("%d",&m);
	for(int i = 1;i <= m;++i)	scanf("%d",&p[i]);
	vector<int> res;
	int last = p[1],pos = 1;res.push_back(last);
	for(int i = 2;i <= m - 1;++i)
	{
		if(f[last][p[i]] != f[last][p[i + 1]] - 1)
		{
			last = p[i];
			pos = i;
			res.push_back(p[i]);
		}
	}
	res.push_back(p[m]);
	printf("%d\n",(int)res.size());
	for(auto& v : res)	printf("%d ",v);
    return 0;
}

D. Kirk and a Binary String

原题大意:给一个二进制字符串s,构造一个等长的字符串t,保证任意两个区间内的子串的最长不降子序列的长度相等.并且t里的0尽量多.
数据范围:
1S20001 \leq |S| \leq 2000 (easy)
1S1051 \leq |S| \leq 10^5

思路

可以想到这样一个性质:对于一个0变成一个1是毫无意义的,不会让答案变得更好,甚至可能破坏性质.整个过程应该只有1变成0.那么整个序列的最长不降序列的长度记作lenlen,00的个数记为cntcnt,那么整个序列里应该有lencntlen-cnt个1可以换成0.如果恰好相等则说明没有1可以换了,就是原串.因为最好情况就是整个不降序列就是一个纯0串.所以两者之差就是可以转换的数了.
考虑怎样的一个1可以被替换掉:如果以他为结尾的最长不降序列的长度恰好是应该修改的个数的话,就说明他是应该修改的最后一个数,因此可以从后往前依次看每个11是否满足这个性质,并修改掉当前还需要修改几个数.其次,还要做一个dpdp求出以1结尾的最长不降子序列的长度,分析到此整个题就比较容易了.

代码

using namespace std;
typedef long long ll;

const int N = 1e5+7;
char s[N];
int f[N],sum[N];
int main()
{
	scanf("%s",s + 1);
	int n =	strlen(s + 1);
	f[0] = 1;
	int cnt = 0;
	for(int i = 1;i <= n;++i)
	{
		f[i] = f[i - 1];sum[i] = sum[i - 1];
		if(s[i] == '1')	f[i] = max(f[i - 1] + 1,sum[i - 1] + 1);
		else	sum[i] = sum[i - 1] + 1,++cnt;
	}
	int len = f[n] - cnt,c = 0;
	for(int i = n;i >= 1;--i)
	{
		if(s[i] == '1' && f[i] == sum[i] + len - c)
		{
			++c;
			s[i] = '0';
		}
	}
	printf("%s",s + 1);
    return 0;
}